#include <bits/stdc++.h>

using namespace std;




struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//根据vector值构建二叉树
TreeNode * gou(vector<int> num){
    if(num.size()==0) return nullptr;
    TreeNode *root=new TreeNode(num[0]);
    queue<TreeNode*> s;
    s.push(root);
    int index=1,len=num.size();
    while(!s.empty()&&index<len){
        TreeNode *p=nullptr,*q=nullptr;
        p=new TreeNode(num[index++]);
        if(index<len) q=new TreeNode(num[index++]);
        TreeNode *r=s.front();s.pop();
        r->left=p;r->right=q;
        s.push(p),s.push(q);
    }
    return root;
}


class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

//就地完成转换
class Solution {
    Node *pre,*head;
public:
    void helper(Node *root){
        if(root==nullptr) return;
        helper(root->left);
        if(pre!=nullptr){
            pre->right=root; 
        }else{
            head=root;
        }
        root->left=pre;
        pre=root;
        helper(root->right);
    }
    Node* treeToDoublyList(Node* root) {
        if(root==nullptr) return nullptr;
        helper(root);
        head->left=pre;
        pre->right=head;
        return head;
    }
};


int main(){




    return 0;
}